1. Field of the Invention
The present invention relates to a branch prediction device, a hybrid branch prediction device, a processor, a branch prediction method, and a branch prediction control program.
2. Related Art
Branch prediction in computer architecture is a function provided in a processor for predicting whether or not a condition branch command branches in a program executing procedure. The processor fetches and executes a command by the branch prediction function before it is actually determined whether or not branching is performed. Particularly, branch prediction is required in a pipelining processor because commands are fetched sequentially in order not to interrupt the pipeline.
As related art of branch prediction devices for performing such branch prediction, first related art (Andre Seznec et al, “Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor” to appear in proceedings of the 29th IEEE-ACM International Symposium on Computer Architecture, 25-29 May 2002, Anchorage, Non-Patent Document 1), and second related art (JP 2003-5956 A, Patent Document 1) have been known.
The first related art discloses an exemplary configuration of a branch prediction device of an active branch prediction system, which is shown in FIG. 15. FIG. 15 is a block diagram showing an example of the first related art of a branch prediction device.
In a branch prediction device 700 shown in FIG. 15, a branch prediction result is generated using the readout results of pattern history tables 720-1, 720-2, and 720-3. Specifically, index information of the pattern history tables 720-1, 720-2, and 720-3 is generated using hash logic circuits 710-1, 710-2, and 710-3 (see pp. 7-8 in Non-Patent Document). In FIG. 15, the hash logic circuits 710-1, 710-2, and 710-3 carry out a hashing operation according to global branch history information from a global branch history 702 (information storing unit) and a branch command address corresponding to an subject command from a command counter 740.
The branch prediction device 700 of the first related art configures a hybrid branch prediction device of “2Bc-gskew” type which outputs the final branch prediction result through selection by a prediction result generation logic 730 from among branch prediction results by multiple types of tables including the pattern history table 720-1 (Meta: global branch prediction device), the pattern history table 720-2 (G1: “e-gskew” type branch prediction device), the pattern history table 720-3 (G1: “e-gskew” type branch prediction device), and the pattern history table 720-3 (BIM: bimodal branch prediction device).
In the second related art (Patent Document 1), a branch prediction device includes an XOR circuit as a hash logic circuit immediately preceding a tagged PHT (Pattern History Table) unit which is a pattern history table (see FIG. 2 of Patent Document 1). The XOR circuit calculates XOR of the branch command address to be executed shown by a program counter and the content of a GHR unit. The GHR (Global History Register) unit is a register which records the history regarding whether or not recently executed branch commands were branched. The calculated XOR is supplied to the tagged PHT (Pattern History Table) unit as an index. The tagged PHT unit is a RAM which stores a tag and a count value with respect to each index which is an output of the XOR circuit. If the count value is 0 or 1, it is predicted not to branch, and if the count value is 2 or 3, it is predicted to branch.
However, in both of the first related art and the second related art, as a hash logic circuit is provided immediately before a pattern history table, there has been a problem that a delay in processing of branch prediction will become worse when an access to the pattern history table is performed, which lowers the processing speed of the processor.
Further, in the branch prediction device of the first related art, when hash logic circuits 710-1, 710-2 and 710-3 perform operations according to a branch command address from a command counter 740, the branch command address from the command counter 740 is not known until immediately before the fetch stage. As such, operations by the hash logic circuits 710-1, 710-2 and 710-3 cannot be performed in advance prior to the fetch stage of the processor pipeline processing. In this way, presence of the hash logic circuits 710-1, 710-2 and 710-3 impede a higher processing speed.
Additionally, if complicated hash logic operations are performed by the hash logic circuits 710-1, 710-2 and 710-3 according to the branch command address when the address has become known after starting the fetch stage of the processor pipeline processing, the arithmetic processing takes time. As such, a delay in the operations by the hash logic circuits causes a delay in branch prediction including an accessing process to the pattern history tables, leading to a delay of the fetch stage itself, and to a delay of the processor, consequently. As delays in branch prediction include delays of the hash logic circuits 710-1, 710-2 and 710-3, a clock cycle of the entire processor is limited due to the delay in branch prediction, which adversely affects the processing speed of the processor.